package cn.lj2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SanSum15 {

    public static void main(String[] args) {
        Solution solution = new SanSum15().new Solution();
    }

    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ans = new ArrayList();
            int l = nums.length;
            if (nums == null||l<3)return ans;
            Arrays.sort(nums);

            for (int i = 0; i < l; i++) {
                if (nums[i]>0) break;
                if (i>0&&nums[i]==nums[i-1]) continue;

                int left = i + 1;
                int right = l - 1;
                while (left<right){
                    int sum = nums[i] + nums[left] + nums[right];
                    if (sum == 0){
                        ans.add(Arrays.asList(nums[i],nums[right],nums[left]));
                        while (left<right&&nums[left]==nums[left+1]) left++;
                        while (left<right&&nums[right]==nums[right-1]) right--;
                        left++;
                        right--;
                    }
                    else if (sum<0) left++;
                    else if (sum>0) right--;
                }
            }
            return ans;
        }
    }
}
